Public key signature protocols are used to verify the signatures appended to messages and thereby verify the authenticity of those messages. Some of these protocols such as El Gamel and DSS, involve a long-term public-private number pair for each user and a per-message public-private number pair specific to each message. The long-term private number is known only to its "owner" while the long-term public number is disseminated at least to those who are to receive messages from the owner. The per-message private number is a random number available only to the owner, while the corresponding public number is transmitted to the message recipient.
Each signature is a function of the long-term private number, the per-message private number and the message itself. The recipient of the message can verify the authenticity thereof by applying a known mathematical algorithm to the long-term public number, the per-message public number, the signature and the message. With this arrangement one cannot compromise the system by intercepting the message and the signature and substituting a bogus message, since the verification algorithm will then fail to authenticate the signature.
More specifically, in an El Gamal system there are a base number g and a prime number p. The long-term public number P.sub.L, is related to the long-term secret number, S.sub.L by EQU P.sub.L =(g.sup.SL).sub.(mod p) ( 1)
Similarly, the per-message public number, P.sub.M, is related to the per-message secret number, S.sub.M by EQU P.sub.M =(g.sup.SM).sub.(mod p) ( 2)
In a typical El Gamel system the signature SIG for a message MSG is generated in accordance with the function: EQU SIG=((S.sub.L *MSG)+S.sub.M)).sub.((mod(p-1)) 3)
The signature is transmitted to the message recipient along with the per-message public number and, of course, the message itself. The recipient verifies the signature by applying a verification function to the signature, the message, the long-term public number and the per-message public number. The verification function will authenticate the signature only if the received message is identical with the original message used by the message originator in generating the signature.
In a system of this type it is essential that the per-message secret number be different for different messages. If it is the same, anyone who receives the signed messages, either legitimately or by interception, can derive the originator's long-term secret number and thereafter impersonate the owner of the number.
The generation of successive, different, per-message random numbers can be accomplished by means of a random-number generator. However, true random-number generators are relatively expensive to implement, especially in the context of low-cost devices, an example being a so-called "smart card" which might be used to "plug into" a system to obtain access thereto.
A pseudo-random-number generator can also be used to generate the single-message number. However, implementation of this arrangement requires the use of non-volatile read/write storage and inexpensive smart cards are incapable of such storage.
Accordingly, it is an object of the present invention to provide a signature system of the El-Gamal or DSS type incorporating novel generation of per-message random-numbers. A more specific object of the invention is to provide a signature arrangement in which the per-message number pair is essentially random in character and is generated without the use of read/write storage registers or hardware-implemented randomnumber generators.